Deterministic, Stash-Free Write-Only ORAM

摘要

Write-Only Oblivious RAM (WoORAM) protocols provide privacy by encrypting thecontents of data and also hiding the pattern of write operations over thatdata. WoORAMs provide better privacy than plain encryption and betterperformance than more general ORAM schemes (which hide both writing and readingaccess patterns), and the write-oblivious setting has been applied to importantapplications of cloud storage synchronization and encrypted hidden volumes. Inthis paper, we introduce an entirely new technique for Write-Only ORAM, calledDetWoORAM. Unlike previous solutions, DetWoORAM uses a deterministic,sequential writing pattern without the need for any "stashing" of blocks inlocal state when writes fail. Our protocol, while conceptually simple, providessubstantial improvement over prior solutions, both asymptotically andexperimentally. In particular, under typical settings the DetWoORAM writes only2 blocks (sequentially) to backend memory for each block written to the device,which is optimal. We have implemented our solution using the BUSE (block devicein user-space) module and tested DetWoORAM against both an encryption onlybaseline of dm-crypt and prior, randomized WoORAM solutions, measuring only a3x-14x slowdown compared to an encryption-only baseline and around 6x-19xspeedup compared to prior work.